package srcInterviewPrep;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;

public final class IntervalScheduling
{
    public static List<Interval> ScheduleIntervals(List<Interval> intervals)
    {
        // null check for intervals
        
        Collections.sort(intervals);
        
        HashMap<Interval, List<Interval>> overlapMap = GetIntervalsOverlapMap(intervals);
        
        LinkedHashSet<Interval> intervalsSet = new LinkedHashSet<Interval>();
        for (Interval i : intervals)
        {
            intervalsSet.add(i);
        }
        
        List<Interval> scheduledIntervals = new ArrayList<Interval>();
        
        while (!intervalsSet.isEmpty())
        {
            Interval i = intervalsSet.iterator().next();
            scheduledIntervals.add(i);
            intervalsSet.remove(i);
            
            for (Interval conflictingInterval : overlapMap.get(i))
            {
                intervalsSet.remove(conflictingInterval);
            }
        }
        
        return scheduledIntervals;
    }
    
    private static HashMap<Interval, List<Interval>> GetIntervalsOverlapMap(List<Interval> intervals)
    {
        HashMap<Interval, List<Interval>> map = new HashMap<Interval, List<Interval>>();
        
        for (Interval i : intervals)
        {
            if (!map.containsKey(i))
            {
                map.put(i, new ArrayList<Interval>());
            }
            
            for (Interval j : intervals)
            {   
                if (i != j)
                {
                    if (!((i.FinishTime <= j.StartTime) || i.StartTime >= j.FinishTime))
                    {
                        map.get(i).add(j);
                    }
                }
            }
        }
        
        return map;
    }
}